A Computational Approach to Number Theory and Algebra - Solution

If you've found anything wrong (or have questions), you can reach me at [email protected].

Chapter 1

1.2 Ideals and greatest common divisors

Exercise 1.8

As $I$ is already closed under addition, it's sufficient to show that $\forall a \in I, -a \in I$ implies $I$ is closed under multiplication with any $z \in \mathbb{Z}$ and verse versa.

On one hand, the closing under addition property already implies that $\forall a \in I, z \in \mathbb{Z}^+, az \in I$ by repeatedly adding $a$ for $z$ times. And this can be easily extended to negative number $z' \in \mathbb{Z}^-$ by repeatedly adding $-a$ for $|z'|$ times since $-a \in I$. Simultaneously, by choosing any $a \in I$, $a + (-a) = 0 \in I$, we can deduce that $a \cdot 0 = 0 \in I$.

On the other hand, $I$ is an ideal instantly implies $\forall a \in I, -a \in I$ by multiplying $a$ with $-1 \in \mathbb{Z}$.

So $I$ is an ideal if and only if all conditions in the question holds.

Exercise 1.9

Observation 1: $\forall a' \gt |a|, a' \nmid a$

Observation 2: $\forall a \in \mathbb{Z}, |a| \mid a$: proof: $1 \cdot a = a \land (-1) \cdot (-a) = a$

(a)

Suppose $\gcd(a, b) = d$ and $\gcd(b, a) = d'$. By definition of $\gcd$ we have $d \mid a \land d \mid b$ and $d' \mid a \land d' \mid b$, thus $d \mid d' \land d' \mid d \Rightarrow d = d'$

(b)

$\gcd(a, b) = |a|$ implies $|a| \mid b$, thus $a \mid b$. When $a \mid b$, we have $|a| \mid a \land |a| \mid b$. By observation 1 we have $\gcd(a, b) = |a|$

(c)

• The first equation: Firstly, $0 \cdot |a| = 0 \Rightarrow |a| \mid 0$. Secondly, by observation 1 and 2 its easy to show that $|a|$ is the maximum integer that divides $a$. So $\gcd(a, 0) = \gcd(a, a) = |a|$.

• The second equation: $1 \mid 1 \land 1 \mid a$ and $1$ is the only divisor of $1$, thus $\gcd(a, 1) = 1$

(d)

Suppose $\gcd(ca, cb) = d$, by theorem 1.8, there exists integers $s, t$ so that $sca + tcb = d$, thus $sa + tb = \frac{d}{c}$. We can easily show that $\frac{d}{|c|}$ is the minimal value for $s'a + t'b$ for integers $s', t'$ by proof of contradiction, thus $\gcd(a, b) = \frac{d}{|c|}$. So $gcd(ca, cb) = |c|\gcd(a, b)$.